import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/5/26
 * Time: 17:26
 */

public class Solution {
    private static int i = 0;
    public static TreeNode createTree(int[] array){
        int cur = array[i];
        TreeNode root = null;
        if(cur == -1){
            i++;
        }else {
            root = new TreeNode(cur);
            i++;
            root.left = createTree(array);
            root.right = createTree(array);
        }
        return root;
    }
    public static int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            root = root.right;
        }
        return root.val;
    }
    public static void main(String[] args) {
        TreeNode root = createTree(new int[]{20, 10, 5, -1,-1,-1, 30, -1, -1});
        System.out.println(kthSmallest(root, 3));
    }
}